package experiment3.huffman;

import java.util.*;

public class Huffman {
    protected class Node {
        Node left;
        Node right;
        Integer weight;
        Character ch;

        Node(Node left, Node right, Character ch, Integer weight) {
            this.left = left;
            this.right = right;
            this.weight = weight;
            this.ch = ch;
        }

        @Override
        public String toString() {
            return "[" + left + "," + weight + "," + right + "]";
        }
    }

    private Node root;
    private HashMap<Character, String> csMap;
    private HashMap<Character, Integer> ciMap;
    private StringBuilder code;

    //词频统计
    private HashMap count(String s) {
        HashMap<Character, Integer> ciMap = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            ciMap.compute(s.charAt(i), (k, v) -> (null == v) ? 1 : v + 1);
        }
        System.out.println(ciMap);
        return ciMap;
    }

    private Node generateHuffmanTree(HashMap<Character, Integer> map) {
        PriorityQueue<Node> priorityQueue = new PriorityQueue(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.weight - o2.weight;
            }
        });

        //将叶子节点添加到优先队列
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            priorityQueue.add(new Node(null, null, entry.getKey(), entry.getValue()));
        }

        //生产哈夫曼树
        while (priorityQueue.size() >= 2) {
            Node left = priorityQueue.poll();
            Node right = priorityQueue.poll();

            priorityQueue.add(new Node(left, right, null, left.weight + right.weight));
        }
        //记录根节点
        return priorityQueue.poll();
    }

    private HashMap decodeTreeNode(Node node) {
        HashMap<Character, String> codeMap = new HashMap<>();
        decodeTreeNodeDFS(root, new StringBuilder('0'), codeMap);
        return codeMap;
    }

    private void decodeTreeNodeDFS(Node node, StringBuilder sb, HashMap<Character, String> codeMap) {
        StringBuilder sb2 = new StringBuilder(sb);
        if (node.left != null) {
            sb2.append('1');
            decodeTreeNodeDFS(node.left, sb2, codeMap);
        }
        if (node.right != null) {
            sb2.append('0');
            decodeTreeNodeDFS(node.right, sb2, codeMap);
        }
        //将字符的编码保存在codeMap中
        codeMap.put(node.ch, sb.toString());
    }

    public void decode(String s) {
        //词频统计
        ciMap = count(s);

        //生成哈夫曼树
        root = generateHuffmanTree(ciMap);

        //对叶子节点进行编码
        csMap = decodeTreeNode(root);
        //将s串进行编码以0-1序列呈现
        code = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            code.append(csMap.get(s.charAt(i)));
        }
    }

    public HashMap getFrequencyTable() {
        return ciMap;
    }

    public Node getHuffmanTreeRoot() {
        return root;
    }

    public HashMap getCodingTable() {
        return csMap;
    }

    public String getCoding() {
        return code.toString();
    }


    //    //随机产生常规字符
//    private static String generateRandomString(int n) {
//        Random random = new Random();
//        String  a = "0123456789qwertyuioplkjhgfdsazxcvbnm";
//        StringBuilder sb = new StringBuilder();
//
//        for (int i =0;i < n;i++){
//            int next =  (random.nextInt(Integer.MAX_VALUE) % a.length());
//            sb.append(a.charAt(next));
//        }
//        return sb.toString();
//    }
    //随机产生可见字符串
    private static String generateRandomString(int n) {
        Random random = new Random();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            char next = (char) (random.nextInt(Integer.MAX_VALUE) % (127 - 32) + 32);
            sb.append(next);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = generateRandomString(scanner.nextInt());

        System.out.println(s);
        System.out.println();
        Huffman huffman = new Huffman();
        huffman.decode(s);
        System.out.println(s);
        System.out.println(huffman.getCoding());
        System.out.println(huffman.getCodingTable());
        System.out.println(huffman.getFrequencyTable());
        System.out.println(huffman.getHuffmanTreeRoot());

    }
}

